package temp;

/**
 * Created by yzy on 2020-04-15 11:48
 */
public class QuickSortQuestion {

    public static void main(String[] args) {

    }

    public void quickSort(int[] arr){
        sort(arr, 0, arr.length-1);
    }

    public void sort(int[] arr, int left, int right){
        if(left >= right){
            return;
        }

        int point = arr[left];
        int i=left;
        int j=right;

        while(i != j){
            // 左边为锚点，先从右边找
            while(j<arr.length && j>point){
                j--;
            }
            while(i<arr.length && i<point){
                i++;
            }

            // 找到以后交换
            if(i < j){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }

        // 最后和锚点交换
        arr[left] = arr[i];
        arr[i] = point;

        sort(arr, left, i-1);
        sort(arr, i+1, right);
    }
}
